import java.util.HashMap;
import java.util.Map;

public class Main {

    // 记忆化搜索的缓存
    private static Map<String, Integer> memo = new HashMap<>();

    // 递归函数，计算给定括号序列可以形成的合法括号序列的数量
    private static int countValidWays(String s) {
        // 如果字符串已经在缓存中，直接返回结果
        if (memo.containsKey(s)) {
            return memo.get(s);
        }

        int n = s.length();
        int count = 0;

        // 尝试在字符串的不同位置添加括号，并递归计算
        for (int i = 0; i < n; i++) {
            // 如果当前字符是左括号或者前面有未匹配的右括号，可以在前面添加右括号
            if (s.charAt(i) == '(' || (i > 0 && s.charAt(i - 1) == ')')) {
                StringBuilder newS = new StringBuilder(s);
                newS.insert(i, ')');
                count += countValidWays(newS.toString());
            }
            // 如果当前字符是右括号或者前面有未匹配的左括号（且不是第一个字符），可以在前面添加左括号
            if (s.charAt(i) == ')' || (i > 0 && s.charAt(i - 1) == '(')) {
                StringBuilder newS = new StringBuilder(s);
                newS.insert(i, '(');
                count += countValidWays(newS.toString());
            }
            // 注意：这里不需要同时考虑在i位置同时添加'('和')'，因为那会导致更长的序列，而我们要求尽可能少地添加括号
        }

        // 如果字符串本身就是合法的括号序列，则计数加1
        if (isValid(s)) {
            count++;
        }

        // 将结果存入缓存
        memo.put(s, count);
        return count;
    }

    // 辅助函数，检查一个括号序列是否合法
    private static boolean isValid(String s) {
        int balance = 0;
        for (char c : s.toCharArray()) {
            if (c == '(') {
                balance++;
            } else if (c == ')') {
                balance--;
            }
            if (balance < 0) {
                return false;
            }
        }
        return balance == 0;
    }

    // 主函数
    public static int countWaysToFormValidBrackets(String s) {
        // 清空缓存（如果需要多次调用，则不应每次都清空）
        memo.clear();
        return countValidWays(s);
    }

    public static void main(String[] args) {
        String s = "((()";
        System.out.println("Number of essentially different ways to form valid brackets: " + countWaysToFormValidBrackets(s));
    }
}